ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/icon/newsgrp/group93c.txt/000126_icon-group-sender _Mon Dec 13 23:57:38 1993.msg

Internet Message Format | 1994-02-02 | 4KB

Received: by cheltenham.cs.arizona.edu; Thu, 16 Dec 1993 23:05:04 MST
Date: 13 Dec 93 23:57:38 GMT
From: dog.ee.lbl.gov!overload.lbl.gov!agate!howland.reston.ans.net!sol.ctr.columbia.edu!news.kei.com!world!ksr![e-mail]  (Tim Peters)
Organization: Kendall Square Research Corp.
Subject: Re: Need help with (simple?) programming problem.
Message-Id: <[e-mail]>
References: <[e-mail]>
Sender: [e-mail]
To: [e-mail]
Status: R
Errors-To: [e-mail]

[e-mail] (Ronald F. Guilmette) writes:
>...
>Assume that I have three strings, i.e. "red ", "green ", and "blue ". Now
>I want to create a generator which will successively yield each unique
>string which contains no more than one instance of each of the original
>strings.  [should produce:]
>
>               ""
>               "red "
>               "green "
>               "blue "
>               "red green "
>               "red blue "
>               "green red "
>               "green blue "
>               "blue red "
>               "blue green "
>               "red green blue "
>               "red blue green "
>               "green red blue "
>               "green blue red "
>               "blue red green "
>               "blue green red "
>
>[& order of generation is unimportant]

Two hints:

1) A small library of simple combinatorial generators can be combined in
   powerful ways.  For example, your problem can be viewed like this:
   given a set of strings, generate each permutation of each subset of
   that set.  Given a generator capable of generating subsets, and
   another capable of generating permutations, you're basically done.

2) Represent the string sets internally as lists of strings, delaying
   conversion to a string representation until output.  The reason is
   that lists are easy to index and pull apart etc, much easier than
   reparsing strings all the time.

Here's a permutation generator (& no, the generators I'm posting aren't
_obvious_ -- but they'll reward the effort of doping them out <wink>):

procedure perms( x ) # generate all permutations of list x
    if *x <= 1 then return x
    suspend x[1] <-> !x & push( perms(x[2:0]), x[1]  )
end

And here's a subset generator:

procedure subsets( x )   # generate all subsets of list x
   local head, tail
   if *x = 0 then return []
   head := x[1]
   tail := x[2:0]
   suspend subsets(tail) | push(subsets(tail), head)
end

Now a function to paste a list of strings together:

procedure list2str( x )  # e.g., ["a", "bc", "d"] -> "abcd"
   local answer
   answer := ""
   every answer ||:= !x
   return answer
end

Then, e.g.,

procedure main()
   every write( list2str( perms( subsets( ["red ","green ","blue "] ) ) ) )
end

writes

[an empty strng was printed on this line]
blue
green
green blue
blue green
red
red blue
blue red
red green
green red
red green blue
red blue green
green red blue
green blue red
blue green red
blue red green

Of course you can package the perms+subsets composition in another
function, etc.  The key idea is just to build it out of simpler
generators.

>P.S.  It probably makes no difference, but in the case of my *real* problem,
>one or more of the "original strings" may not actually be strings at all.
>They may instead be generators which produce various strings.

That may be a lot harder to deal with.  If possible, it would probably be
best to materialize the sequences into lists, so that they can be fiddled
via simple generators like the above.

combinatorially y'rs  - tim

Tim Peters   [e-mail]
not speaking for Kendall Square Research Corp